/*************************************************************************
	> File Name: skip_list.cpp
	> Author: 
	> Mail: 
	> Created Time: Mon 12 Aug 2024 10:03:40 AM CST
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <inttypes.h>
#define MAX_LEVEL 10
#define min(a, b) ((a) < (b) ? (a) : (b))

typedef struct Node {
	int key, level;
	struct Node *next, *down, *up;
} Node;

typedef struct SkipList {
	Node *head, *tail;
	int max_level;
} SkipList;

Node *getNewNode(int key, int level) {
	int n = level;
	Node *nodes = (Node *)malloc(sizeof(Node) * n);
	for(int i = 0; i < n; ++i) {
		nodes[i].key = key;
		nodes[i].level = i;
		nodes[i].next = NULL;
		nodes[i].down = (i ? nodes + i - 1 : NULL);
		nodes[i].up = (i + 1 < n ? nodes + i + 1 : NULL);
	}
	return nodes + n - 1;
}

SkipList *initSkipList(int n) {
	SkipList *s = (SkipList *)malloc(sizeof(SkipList));
	s->head = getNewNode(INT32_MIN, n);
	s->tail = getNewNode(INT32_MAX, n);
	s->max_level = n;
	Node *p = s->head, *q = s->tail;
	while(p) {
		p->next = q;
		p = p->down;
		q = q->down;
	}
	while (s->head->level != 0) s->head = s->head->down;
	return s;
}

Node *findValue(SkipList *s, int x) {
	Node *p = s->head;
	while(p && p->key != x) {
		if(p->next->key <= x) p = p->next;
		else p = p->down;
	}
	return p;
}

double randDouble() {
	#define N 1000000
	return (rand() % N) * 1.0 / N;
	#undef N
}

int randLevel(SkipList *s) {
	int level = 1;
	double p = 1.0 / 2.0;
	if(randDouble() < p) level += 1;
	return min(s->max_level, level);
}

void insert(SkipList *s, int x) {
	// int level = randLevel(s);
	int level = rand() % 3 + 1;
	// printf("rand level = %d\n", level);
	while (s->head->level + 1 < level) s->head = s->head->up;
	Node *node = getNewNode(x, level);
	Node *p = s->head;
	while(p->level != node->level) p = p->down;
	while(p) {
		while(p->next->key < node->key) p = p->next;
		node->next = p->next;
		p->next = node;
		p = p->down;
		node = node->down;
	}
	return ;
}

void outPut_1(SkipList *s) {
	Node *p = s->head , *q;
	while(p) {
		printf("Level %d = ", p->level);
		for(q = p; q; q = q->next) {
			if(q->key == INT32_MIN || q->key == INT32_MAX) continue;
			printf("%4d", q->key);
		}
		printf("\n");
		p = p->down;
	}
	return ;
}

void output(SkipList *s) {
    Node *p = s->head;
    int len = 0;
    for (int i = 0; i <= s->head->level; i++) {
        len += printf("%4d", i);
    }
    printf("\n");
    for (int i = 0; i < len; i++) printf("-");
    printf("\n");
    while (p->level > 0) p = p->down;
    while (p) {
        bool flag = (p->key != INT32_MIN && p->key != INT32_MAX);
        for (Node *q = p; flag && q; q = q->up) {
            printf("%4d", q->key);
        }
        if (flag) printf("\n");
        p = p->next;
    }
    return ;
}

void clearNode(Node *p) {
	if(p == NULL) return ;
	free(p);
	return ;
}

void clearSkipList(SkipList *s) {
	Node *p = s->head, *q;
	while (p->level != 0) p = p->down;
	while(p) {
		q = p->next;
		clearNode(p);
		p = q;
	}
	free(s);
	return ;
}
int main() {
	srand(time(0));
	int x;
	SkipList *s = initSkipList(MAX_LEVEL);
	while(~scanf("%d", &x)) {
		if(x == -1) break;
		insert(s, x);
	}
	outPut_1(s);
	output(s);
	while (~scanf("%d", &x)) {
        Node *p = findValue(s, x);
        printf("find result : ");
        if (p) {
            printf("key = %d, level = %d\n", p->key, p->level);
        } else {
            printf("NULL\n");
        }
    }
	clearSkipList(s);
	return 0;
}

